home *** CD-ROM | disk | FTP | other *** search
/ Cre@te Online 2000 December / Cre@teOnline CD05.iso / MacSoft / XML Instance.sea / XML Instance / Required / ccs_util.jar / com / commerceone / util / string / StringTable.class (.txt) next >
Encoding:
Java Class File  |  1999-12-09  |  2.7 KB  |  109 lines
  1. package com.commerceone.util.string;
  2.  
  3. public class StringTable {
  4.    static final int DEFAULT_CACHE_SIZE = 1009;
  5.    static final double LOAD_FACTOR = 0.7;
  6.    Bucket[] table;
  7.    Bucket mru;
  8.    int cacheFree;
  9.  
  10.    public StringTable(int cacheSize) {
  11.       this.mru = new Bucket();
  12.       this.table = new Bucket[cacheSize];
  13.       this.cacheFree = (int)((double)this.table.length * 0.7);
  14.       this.mru.nextMru = this.mru;
  15.       this.mru.prevMru = this.mru;
  16.    }
  17.  
  18.    public StringTable() {
  19.       this(1009);
  20.    }
  21.  
  22.    public String convert(char[] buf, int start, int end, boolean permanent) {
  23.       int i = hash(buf, start, end) % this.table.length;
  24.       Bucket bucket = this.table[i];
  25.       if (bucket != null) {
  26.          for(Bucket p = bucket.nextBucket; p != bucket; p = p.nextBucket) {
  27.             if (p.matches(buf, start, end)) {
  28.                if (p.nextMru != null) {
  29.                   unlinkMru(p);
  30.                   if (permanent) {
  31.                      p.nextMru = null;
  32.                   } else {
  33.                      linkMru(this.mru, p);
  34.                   }
  35.                }
  36.  
  37.                return p.string;
  38.             }
  39.          }
  40.       } else {
  41.          bucket = new Bucket();
  42.          bucket.nextBucket = bucket.prevBucket = bucket;
  43.          this.table[i] = bucket;
  44.       }
  45.  
  46.       Bucket tem;
  47.       if (this.cacheFree <= 0) {
  48.          if (this.mru.nextMru == this.mru) {
  49.             for(int j = 0; j < this.table.length; ++j) {
  50.                Bucket h = this.table[j];
  51.                if (h != null) {
  52.                   for(Bucket p = h.nextBucket; p != h; p = p.nextBucket) {
  53.                      linkMru(this.mru, p);
  54.                   }
  55.  
  56.                   h.nextBucket = h.prevBucket = h;
  57.                }
  58.             }
  59.          }
  60.  
  61.          tem = this.mru.prevMru;
  62.          unlinkMru(tem);
  63.          tem.prevBucket.nextBucket = tem.nextBucket;
  64.          tem.nextBucket.prevBucket = tem.prevBucket;
  65.          if (permanent) {
  66.             tem.nextMru = null;
  67.          } else {
  68.             linkMru(this.mru, tem);
  69.          }
  70.       } else {
  71.          this.cacheFree += -1;
  72.          tem = new Bucket();
  73.          if (!permanent) {
  74.             linkMru(this.mru, tem);
  75.          }
  76.       }
  77.  
  78.       tem.string = new String(buf, start, end);
  79.       char[] chars = new char[end - start];
  80.       System.arraycopy(buf, start, chars, 0, chars.length);
  81.       tem.chars = chars;
  82.       tem.nextBucket = bucket.nextBucket;
  83.       tem.nextBucket.prevBucket = tem;
  84.       tem.prevBucket = bucket;
  85.       bucket.nextBucket = tem;
  86.       return tem.string;
  87.    }
  88.  
  89.    private static final void unlinkMru(Bucket s) {
  90.       s.prevMru.nextMru = s.nextMru;
  91.       s.nextMru.prevMru = s.prevMru;
  92.    }
  93.  
  94.    private static final int hash(char[] buf, int start, int end) {
  95.       int h;
  96.       for(h = 0; start != end; h += (h << 5) + (buf[start++] & 255)) {
  97.       }
  98.  
  99.       return h & Integer.MAX_VALUE;
  100.    }
  101.  
  102.    private static final void linkMru(Bucket after, Bucket s) {
  103.       s.nextMru = after.nextMru;
  104.       s.nextMru.prevMru = s;
  105.       s.prevMru = after;
  106.       after.nextMru = s;
  107.    }
  108. }
  109.